Round Overview
Discuss this match
We only care about the key positions modulo 7 to record notes. So, we can take all the keys mod 7, put them in a set, and return the length.
1 2 3 4
class Xylophone(): def countKeys(self, keys): return len(set(x % 7 for x in keys))
A 2^k * n * m solution is obvious, but it is a bit too slow for this problem. How can we speed this up? We can take advantage of preprocessing to get it faster. Namely, we can pre-compute the existing topmost/bottomost/leftmost/rightmost landmarks (‘O’) so we don’t need to redo our work. Then, when considering a configuraiton, we only need to do O(k) work to update these positions. See the code below for more details.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class XMarksTheSpot {
public int countArea(String[] board) {
int n = board.length;
int m = board[0].length();
int mnx = n, mxx = -1, mny = m, mxy = -1;
int[] px = new int[21];
int[] py = new int[21];
int idx = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i].charAt(j) == 'O') {
mnx = Math.min(i, mnx);
mxx = Math.max(i, mxx);
mny = Math.min(j, mny);
mxy = Math.max(j, mxy);
} else if (board[i].charAt(j) == '?') {
px[idx] = i;
py[idx] = j;
idx++;
}
}
}
int ret = 0;
for (int i = 0; i < 1 << idx; i++) {
int cmnx = mnx, cmxx = mxx, cmny = mny, cmxy = mxy;
for (int j = 0; j < idx; j++) {
if (((i >> j) & 1) == 1) {
cmnx = Math.min(cmnx, px[j]);
cmxx = Math.max(cmxx, px[j]);
cmny = Math.min(cmny, py[j]);
cmxy = Math.max(cmxy, py[j]);
}
}
ret += (cmxx - cmnx + 1) * (cmxy - cmny + 1);
}
return ret;
}
}
This should remind you of balanced parenthesis. For instance, the leaders are “opening parenthesis”, and each other person (which I’ll denote as “followers”) in the room is a closing parenthesis. We need each other person to be in the room of some leader, so this analogous to saying that the prefix must have nonnegative weight (i.e. there must be at least as many leaders as there are followers). In this case an opening parenthesis has weight size-1, and a closing parenthesis has weight -1, and we want to count the number of balanced parenthesis such that no prefix has negative weight, the overall weight is zero, and there are room opening parenthesis. We can do this by dp, by keeping track of the “balance” at each step. See the code for more details.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;
public class XYZCoder {
public int mod = 1000000007;
public int countWays(int room, int size) {
int[] dp = new int[room * size + 1];
dp[0] = 1;
for (int left = 1; left <= room * size; left++) {
int[] next = new int[room * size + 1];
for (int balance = 0; balance <= room * size; balance++) {
int ret = 0;
if (balance + size - 1 < dp.length) ret = (ret + dp[balance + size - 1]) % mod;
if (balance > 0) ret = (ret + dp[balance - 1]) % mod;
next[balance] = ret;
}
dp = next;
}
long x = dp[0];
for (int i = 1; i <= room; i++) x = x * i % mod;
return (int) x;
}
}
An obvious condition is that if your friend is a room winner, you return 1. Another obvious condition is that your friend can only be in rooms where the room winner has a lower rank than friendPlace. What other conditions do we need?
First, let’s sort the rooms by leaders. For example, the first sample would be {1,2,5}, with 2 people in each room. Now, let’s look at the person who placed 6th. They can’t possibly go in the first two rooms, since that would force someone with place less than 5 to go into the last room, which would make 5 not the leader. So, the idea is that places 1-4 must be in the first 2 rooms. We can note that if the room winner of the i-th room is roomSize * i + 1, then everyone from place 1 to roomSize*i must be in the first i-1 rooms. So, we can come up with the solution below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;
import java.util.HashSet;
public class FindingFriend {
public int find(int roomSize, int[] leaders, int friendPlace) {
for (int i = 0; i < leaders.length; i++) {
if (leaders[i] == friendPlace) return 1;
}
Arrays.sort(leaders);
int count = 0;
for (int i = 0; i < leaders.length; i++) {
if (leaders[i] > friendPlace) break;
if (leaders[i] == roomSize * i + 1)
count = 0;
count++;
}
return count;
}
}
Parsing the math leads to a graph theory problem. Count the number of graphs with n nodes, where each node has one outgoing edge, and exactly k nodes are part of a cycle. To count this, we can do dp or use math. For the math approach, we first choose the k nodes that will be part of a cycle, and link them together. There are (n choose k) ways to choose the nodes, and k! ways to link them together (you can see this by noticing permutations can be decomposed into cycles). For the second part, we have n nodes with k specified roots, and we want to know the number of forests we can form. This number can be computed as k * n^(n-k-1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class CrazyFunctions {
public int mod = 1000000007;
public long pow(long b, long e) {
long r = 1;
while (e > 0) {
if (e % 2 == 1) r = r * b % mod;
b = b * b % mod;
e >>= 1;
}
return r;
}
public int count(int n, int k) {
long[] fact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
long ans = fact[n] * pow(fact[n - k], mod - 2) % mod;
ans = ans * k % mod;
ans = ans * pow(n, n - k + mod - 2) % mod;
return (int) ans;
}
}
This problem can be split into many small parts. Namely, first, we should compute f(i,j) = probability that the i-th card will be the last card played and it is played in the j-th slot. After this, we can compute g(i,j) = expected value of prize given that i-th card was the last card played in the j-th slot. f(i,j) can be computed using dp or inclusion/exclusion. g(i,j) takes advantage of the fact that many events become independent and uniform when conditioned on the event that f(i,j) happens.
[https://www.youtube.com/watch?v=tp_BWzhwIdU]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.util.Arrays;
public class AnyNumber {
public int mod = 1000000007;
public long INV2 = 500000004;
public long[][] comb;
public String[] cards;
public int[] blank;
public long[] inv, fact, ifact;
public long[] val;
public long[] pow10;
public int total;
public int findExpectation(String[] _cards, int[] _blank) {
cards = _cards;
blank = _blank;
total = 0;
for (int x: blank) total += x;
int mxn = 3001;
inv = new long[mxn];
fact = new long[mxn];
ifact = new long[mxn];
inv[1] = 1;
fact[0] = 1;
ifact[0] = 1;
for (int i = 2; i < mxn; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for (int i = 1; i < mxn; i++) fact[i] = fact[i - 1] * i % mod;
for (int i = 1; i < mxn; i++) ifact[i] = ifact[i - 1] * inv[i] % mod;
comb = new long[mxn][mxn];
comb[0][0] = 1;
for (int i = 1; i < mxn; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++)
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
}
pow10 = new long[mxn];
pow10[0] = 1;
for (int i = 1; i < mxn; i++) pow10[i] = pow10[i - 1] * 10 % mod;
val = new long[cards.length];
for (int i = 0; i < cards.length; i++) {
for (int j = 0; j < cards[i].length(); j++) {
val[i] = (val[i] + (cards[i].charAt(j) - '0') * pow10[cards[i].length() - j - 1]) % mod;
}
}
dp1 = new long[51][51][51];
for (long[][] x: dp1)
for (long[] y: x) Arrays.fill(y, -1);
long ans = 0;
for (int last = 0; last < total && last < cards.length; last++) {
for (int slot = 0; slot < blank.length; slot++) {
if (blank[slot] > last + 1) continue;
// probability that card is last in slot
long prob = f(last, slot);
// expected value given last card and slot given that event
long value = g(last, slot);
ans = (ans + prob * value) % mod;
}
}
return (int) ans;
}
public long f(int card, int row) {
if (card == 0 && blank[row] == 1) {
return inv[total];
}
long[] nways = new long[card + 1];
nways[0] = 1;
for (int i = 0; i < blank.length; i++) {
long[] next = new long[card + 1];
if (i == row) {
for (int j = 0; j + blank[i] - 1 <= card; j++) {
next[j + blank[i] - 1] = nways[j] * comb[j + blank[i] - 1][j] % mod * blank[i] % mod * fact[blank[i] - 1] % mod;
}
} else {
for (int j = 0; j < blank[i]; j++) {
for (int k = 0; k + j <= card; k++) {
next[j + k] = (next[j + k] + nways[k] * comb[blank[i]][j] % mod * fact[j] % mod * comb[j + k][j]) % mod;
}
}
}
nways = next;
}
return nways[card] * ifact[total] % mod * fact[total - card - 1] % mod;
}
public long g(int card, int row) {
if (blank[row] == 1) return val[card];
long ret = 0;
for (int i = 0; i <= card; i++) {
long prob1 = (i == card) ? 1 : ((blank[row] - 1) * inv[card] % mod);
for (int whichpos = 0; whichpos < blank[row]; whichpos++) {
long val = 0;
if (i != card) {
long pp = whichpos * inv[blank[row] - 1] % mod;
val = (val + h(i, card - 1, whichpos) * (1 - pp + mod)) % mod;
if (whichpos > 0) val = (val + h(i, card - 1, whichpos - 1) * pp % mod * pow10[cards[card].length()]) % mod;
} else {
val = (val + h(i, card - 1, whichpos));
}
ret = (ret + prob1 * val % mod * inv[blank[row]]) % mod;
}
}
return ret;
}
public long[][][] dp1;
public long h(int exclude, int cur, int below) {
if (cur == -1 || below == 0) return val[exclude];
int avail = cur + 1 - (exclude <= cur ? 1 : 0);
if (below > avail) return 0;
if (dp1[exclude][cur][below] != -1) return dp1[exclude][cur][below];
if (exclude == cur) return h(exclude, cur - 1, below);
long probbelow = below * inv[avail] % mod;
dp1[exclude][cur][below] = (h(exclude, cur - 1, below - 1) * probbelow % mod * pow10[cards[cur].length()] + h(exclude, cur - 1, below) * (1 - probbelow + mod)) % mod;
return dp1[exclude][cur][below];
}
}